/**
 * 
 */

/**
 * @author Medrano
 *
 */
public class HeapPriorityQueue<E> extends AbstractPriorityQueue<E>{
	
	
	public Object datos[];
	public int size;
	
	public HeapPriorityQueue(int setsize){		
		datos = new Object[setsize];
		size = 0;
	}
	
	
	@Override
	public void add(E value) {
		
			int pos = size;             // virtual position of value
	        int pPos = (pos - 1) / 2;   // position of parent
	        size++;
	        Comparable<E> compValue = (Comparable<E>) value;
	        while(pos > 0 && compValue.compareTo((E)datos[pPos]) < 0) {
	            datos[pos] = datos[pPos]; // move parent into position
	            pos = pPos;             // and step upward
	            pPos = (pos - 1) / 2;
	        }
	        datos[pos] = value;          // place value in final position
		
	}

	@Override
	public void clear() {
		// TODO Auto-generated method stub
		
	}

	public void offer(E value) {
		int pos = size;             // virtual position of value
        int pPos = (pos - 1) / 2;   // position of parent
        size++;
        Comparable<E> compValue = (Comparable<E>) value;
        while(pos > 0 && compValue.compareTo((E)datos[pPos]) < 0) {
            datos[pos] = datos[pPos]; // move parent into position
            pos = pPos;             // and step upward
            pPos = (pos - 1) / 2;
        }
        datos[pos] = value;          // place value in final position
	}
	
	

	@Override
	public E remove() {
		E ret = (E) datos[0];
        size--;                   // move last item to root,
        Comparable<E> toTrickle = (Comparable<E>) datos[size]; // trickle it down
        datos[size] = null;
        int pos = 0;
        while(true) {
            int less = 2 * pos + 1; // determine lesser of children
            if(less >= size) break;
            Comparable<E> left = (Comparable<E>) datos[less];
            if(less + 1 < size && left.compareTo((E)datos[less + 1]) > 0) {
                less++;
            }

           if(toTrickle.compareTo((E)datos[less]) < 0) break;
            datos[pos] = datos[less];
            pos = less;
        }
        datos[pos] = (E) toTrickle;

       return ret;
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return size;
	}


	@Override
	public E getFirst() {
		// TODO Auto-generated method stub
		return null;
	}
	
	public String toString(){
		String desc="";
		for(int i =0; i<size; i++){
			desc+=datos[i].toString();
		}
		return desc;
	}
	
	

	
	
}
